package leetcode.editor.offer;

// 68. 树中两个节点的最低公共祖先
// https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
class ErChaSouSuoShuDeZuiJinGongGongZuXianLcof {
    public static void main(String[] args) {
        Solution solution = new ErChaSouSuoShuDeZuiJinGongGongZuXianLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return traversal(root, p, q);
        }

        public TreeNode traversal(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) {
                return null;
            }

//            if ((root.val >= p.val && root.val <= q.val) || (root.val <= p.val && root.val >= q.val)) return root;

            if (root.val > p.val || root.val > q.val) {
                TreeNode left = traversal(root.left, p, q);
                if (left != null) {
                    return left;
                }
            }

            if (root.val < p.val || root.val < q.val) {
                TreeNode right = traversal(root.right, p, q);
                if (right != null) {
                    return right;
                }
            }


            return root;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
